/**
 * 
 */
package edu.umd.clip.lm.util;

import java.util.*;

/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class SortedRingBuffer<T> extends RingBuffer<T> {
	private Comparator<?super T> comp;
	
	public SortedRingBuffer(T[] buffer, Comparator<? super T> comp) {
		this(buffer, buffer.length, comp);
	}
	
	public SortedRingBuffer(T[] buffer, int size, Comparator<? super T> comp) {
		super(buffer, size);
		this.comp = comp;
	}

	public SortedRingBuffer(T[] buffer, int size) {
		this(buffer, size, null);
	}

	public SortedRingBuffer(T[] buffer) {
		this(buffer, buffer.length, null);
	}

	SortedRingBuffer() {
		
	}
	
	protected void putElement(T e) {
		++size;
		if (size > 1) {
			if (head < tail) {
				int pos = Arrays.binarySearch(buffer, head, tail, e, comp);
				if (pos < 0) pos = -(pos + 1);
				if (pos - head < tail - pos) {
					// shift the first part to the beginning
					if (head == 0) {
						head = buffer.length-1;
						if (pos == 0) {
							buffer[head] = e;
							return;
						}
						buffer[head] = buffer[0];
						System.arraycopy(buffer, 1, buffer, 0, pos);
					} else {
						System.arraycopy(buffer, head, buffer, head-1, pos - head);
						--head;
					}
					buffer[pos-1] = e;
				} else {
					// shift the last part to the end
					System.arraycopy(buffer, pos, buffer, pos+1, tail - pos);
					buffer[pos] = e;
					if (++tail == buffer.length) {
						tail = 0;
					}
				}
			} else {
				// the items wrap around
				int pos1 = Arrays.binarySearch(buffer, head, buffer.length, e, comp);
				if (pos1 < 0) {
					pos1 = -(pos1 + 1);
				}
				int relativePos = 0;
				int pos2 = 0;
				if (pos1 == buffer.length) {
					pos2 = Arrays.binarySearch(buffer, 0, tail, e, comp);
					if (pos2 < 0) {
						pos2 = -(pos2+1);
					}
					relativePos = buffer.length - head + pos2;
				} else {
					relativePos = pos1 - head;
				}
				
				if (relativePos * 2 <= size) {
					// shift the beginning
					System.arraycopy(buffer, head, buffer, head-1, pos1 - head);
					--head;
					if (pos1 != buffer.length) {
						buffer[pos1-1] = e;
					} else { 
						if (pos2 > 0) { 
							buffer[buffer.length-1] = buffer[0];
							System.arraycopy(buffer, 1, buffer, 0, pos2);
							buffer[pos2] = e;
						} else {
							buffer[buffer.length-1] = e;
						}
					}
				} else {
					// shift the ending
					System.arraycopy(buffer, pos2, buffer, pos2+1, tail - pos2);
					if (++tail == buffer.length) {
						tail = 0;
					}
					if (pos1 == buffer.length) {
						// no need to touch the first part
						buffer[pos2] = e;
					} else {
						buffer[0] = buffer[buffer.length-1];
						System.arraycopy(buffer, pos1, buffer, pos1+1, buffer.length - 1 - pos1);
						buffer[pos1] = e;
					}
				}
			}
		} else {
			head = 0;
			tail = 1;
			buffer[0] = e;
		}
	}
	
	@Override
	public Object clone() {
		SortedRingBuffer<T> copy = new SortedRingBuffer<T>();
		copyTo(copy);
		return copy;
	}

	protected void copyTo(SortedRingBuffer<T> copy) {
		super.copyTo(copy);
		copy.comp = comp;
	}

	public static void main(String[] args) {
		final int size = 20;
		Integer[] arr = new Integer[size];
		for(int i=0; i<size; ++i) {
			arr[i] = (int) Math.round(Math.random() * size * 2);
		}
		Arrays.sort(arr);
		RingBuffer<Integer> buff = new SortedRingBuffer<Integer>(arr);
		System.out.println(buff);
		for(int i=0; i<30; ++i) {
			int first = buff.poll();
			Integer num = (int) Math.round(Math.random() * size * 2);
			buff.offer(num);
			System.out.printf("took %d, added %d\n", first, num);
			System.out.println(buff);
		}
	}
}
